原题链接:http://poj.org/problem?id=3415
题目大意:给定两个字符串和,求两者长度至少为的公共子串的数量。
数据范围:
多组测试数据
字符集只有字母
前面写过一个求公共子串长度的题POJ 2217这个题的处理方法其实也是同理,直接两者粘一起就行了。
由于说范围太大了,所以这个题大概的也就的复杂度。
对于有一个重要的结论:对于两个位置和来说,如果有,则就是之间的最小的。对于每一个位置来说,如果他和下一位的的长度至少为的话,那么假设他是合法的,贡献就会增加,把其中个看成个,剩下的个是额外对应进去的。对于实际的答案统计来说,还需要判断两边是否是来自和,所以如果这里直接全部把贡献统计进去会很混乱。所以要分成两种情况进行统计,这里定义一个函数,第一次只把是是左半部分的加入贡献,第二次只把是右边的加入贡献。但是这种统计方法是直接把长度之外的部分也统计进贡献的,假如说下一位的增大了,前面的多余部分是没问题的,但是如果减小了,会导致贡献有误。
对特定的的来说他应该是整个区间的最小值,但是如果往后拓展的同时,发现有某一个比前面都小,就说明:前面加进去的贡献是有多余的部分的,因为前面的算出来的不并正确,不是真正的最小值。对于单个的函数来说,我们发现如果满足递增的性质的话,贡献是可以一直累加的,但是显然情况不会有这么好,于是可以通过单调栈来维护一个单调上升的集合。如果有违反单调性质的,则在栈中删去的同时,还维护一个之前已经有过的即在里选了几个之前的位置,之后如果有影响的,要把这段全加进去去掉相应的贡献。
最后把贡献加进答案的时候要特别看一下,因为这里的是两个情况,所以最后加答案还要看下一位(就是的定义里的下一位)是不是另外一边的,如果是才会把答案统计进去,否则没意义,因为不能自己和自己求公共子串。
代码:
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
using namespace std;
typedef long long ll;
const int N = 2e5+7;
int lcp[N],sa[N],stk[N][2];
namespace SA
{
int rank[N],tmp[N];
int n,k;
bool sa_cmp(int i,int j)
{
if(rank[i] != rank[j]) return rank[i] < rank[j];
else
{
int ri = i + k <= n ? rank[i + k] : -1;
int rj = j + k <= n ? rank[j + k] : -1;
return ri < rj;
}
}
void build_sa(string& s)
{
n = s.size();
for(int i = 0;i <= n;++i)
{
sa[i] = i;
rank[i] = i < n ? s[i] : -1;
}
for(k = 1;k <= n;k *= 2)
{
sort(sa,sa + 1 + n,sa_cmp);
tmp[sa[0]] = 0;
for(int i = 1;i <= n;++i) tmp[sa[i]] = tmp[sa[i - 1]] + sa_cmp(sa[i - 1],sa[i]);
for(int i = 0;i <= n;++i) rank[i] = tmp[i];
}
}
bool contain(string& s,string& T)
{
int l = 0,r = s.size();
while(l < r)
{
int mid = l + r >> 1;
if(s.compare(sa[mid],T.size(),T) < 0) l = mid + 1;
else r = mid;
}
return s.compare(sa[l],T.size(),T) == 0;
}
void build_lcp(string& s)
{
n = s.size();
for(int i = 0;i <= n;++i) rank[sa[i]] = i;
int h = 0;
lcp[0] = 0;
for(int i = 0;i < n;++i)
{
int j = sa[rank[i] - 1];
if(h > 0) --h;
for(;j + h < n && i + h < n;++h)
if(s[j + h] != s[i + h])
break;
lcp[rank[i] - 1] = h;
}
}
}
ll slove(string& s,int k,int left,bool is_sa)
{
ll res = 0,tmp = 0;
int n = s.size(),top = 0;
for(int i = 0;i < n;++i)
{
if(lcp[i] < k) top = 0,tmp = 0;
else
{
int sz = 0;
if((is_sa && sa[i] < left) || (!is_sa && sa[i] > left))
{
++sz;
tmp += lcp[i] - k + 1;
}
while(top > 0 && lcp[i] <= stk[top - 1][0])
{
--top;
tmp -= stk[top][1] * (stk[top][0] - lcp[i]);
sz += stk[top][1];
}
if(sz)
{
stk[top][0] = lcp[i];
stk[top][1] = sz;
++top;
}
if((is_sa && sa[i + 1] > left) || (!is_sa && sa[i + 1] < left))
res += tmp;
}
}
return res;
}
int main()
{
ios::sync_with_stdio();cin.tie(0);
int k;
while(cin >> k,k)
{
string a,b;cin >> a >> b;
int n = a.size(),m = b.size();
int L = n + m + 1;
string s = a + '\0' + b;
SA::build_sa(s);
SA::build_lcp(s);
cout << slove(s,k,n,1) + slove(s,k,n,0) << endl;
}
return 0;
}